#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/3 23:43
# @USER    : Shengji He
# @File    : 3SumClosest.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        """
        Given an array nums of n integers and an integer target,
        find three integers in nums such that the sum is closest to target.
        Return the sum of the three integers. You may assume that each input would have exactly one solution.

        :param nums: List[int]
        :param target: int
        :return: int

        Example:
            Input: nums = [-1,2,1,-4], target = 1\n
            Output: 2\n
            Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

        Constraints:
            - 3 <= nums.length <= 10^3
            - -10^3 <= nums[i] <= 10^3
            - -10^4 <= target <= 10^4
        """
        # diff = 10e5
        # ans = None
        # nums.sort()
        # for i in range(len(nums) - 2):
        #     # if i > 0 and nums[i] == nums[i - 1]:
        #     #     continue
        #     s, e = i + 1, len(nums) - 1
        #     while s < e:
        #         if abs(nums[s] + nums[e] + nums[i] - target) < diff:
        #             diff = abs(nums[s] + nums[e] + nums[i] - target)
        #             ans = nums[i] + nums[s] + nums[e]
        #             # while s < e and nums[s] == nums[s + 1]:
        #             #     s += 1
        #             # while s < e and nums[e] == nums[e - 1]:
        #             #     e -= 1
        #             # s += 1
        #             # e -= 1
        #         elif nums[s] + nums[e] + nums[i] > target:
        #             # while s < e and nums[e] == nums[e - 1]:
        #             #     e -= 1
        #             e -= 1
        #         else:
        #             # while s < e and nums[s] == nums[s + 1]:
        #             #     s += 1
        #             s += 1
        # return ans
        nums.sort()
        res = sum(nums[:3])
        for i in range(len(nums) - 2):
            if i >= 1 and nums[i] == nums[i - 1]:
                continue
            s, e = i + 1, len(nums) - 1

            if nums[i] + nums[e - 1] + nums[e] <= target:
                s = e - 1
            elif nums[i] + nums[s] + nums[s + 1] >= target:
                e = s + 1
            while s < e:
                cur = nums[i] + nums[e] + nums[s]
                if abs(cur - target) < abs(res - target):
                    res = cur
                if cur > target:
                    e -= 1
                elif cur < target:
                    s += 1
                else:
                    return target
        return res


if __name__ == '__main__':
    S = Solution()
    nums = [13, 2, 0, -14, -20, 19, 8, -5, -13, -3, 20, 15, 20, 5, 13, 14, -17, -7, 12, -6, 0, 20, -19, -1, -15, -2, 8,
            -2, -9, 13, 0, -3, -18, -9, -9, -19, 17, -14, -19, -4, -16, 2, 0, 9, 5, -7, -4, 20, 18, 9, 0, 12, -1, 10,
            -17, -11, 16, -13, -14, -3, 0, 2, -18, 2, 8, 20, -15, 3, -13, -12, -2, -19, 11, 11, -10, 1, 1, -10, -2, 12,
            0, 17, -19, -7, 8, -19, -17, 5, -5, -10, 8, 0, -12, 4, 19, 2, 0, 12, 14, -9, 15, 7, 0, -16, -5, 16, -12, 0,
            2, -16, 14, 18, 12, 13, 5, 0, 5, 6]

    # nums = [0, 2, 1, -3]
    # nums = [-1, 2, 1, -4]
    target = -59
    # target = 1
    print(S.threeSumClosest(nums, target))
    print('done')
